package math;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
 * 请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
 * <p>
 * 示例 1：
 * 输入：n = 13
 * 输出：4
 * 解释：总共有 9 个组，将 1 到 13 按数位求和后这些组分别是：
 * [1,10]，[2,11]，[3,12]，[4,13]，[5]，[6]，[7]，[8]，[9]。总共有 4 个组拥有的数字并列最多。
 * <p>
 * 示例 2：
 * 输入：n = 2
 * 输出：2
 * 解释：总共有 2 个大小为 1 的组 [1]，[2]。
 * <p>
 * 示例 3：
 * 输入：n = 15
 * 输出：6
 * <p>
 * 示例 4：
 * 输入：n = 24
 * 输出：5
 *
 * @author Jisheng Huang
 * @version 20250423
 */
public class CountLargestGroup_1399 {
    /**
     * 给你一个整数 n 。请你先求出从 1 到 n 的每个整数 10 进制表示下的数位和（每一位上的数字相加），然后把数位和相等的数字放到同一个组中。
     * 请你统计每个组中的数字数目，并返回数字数目并列最多的组有多少个。
     *
     * @param n the given integer to count from 1 to n
     * @return the max number of size that the sum of each digit of each number
     */
    public static int countLargestGroup(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        int maxVal = 0;

        // Loop from 1 to n
        for (int i = 1; i <= n; ++i) {
            int key = 0;
            // Assign the number to a temp variable
            int i0 = i;

            // Sum up each digit in a number
            while (i0 != 0) {
                key += i0 % 10;
                i0 /= 10;
            }

            map.put(key, map.getOrDefault(key, 0) + 1);
            maxVal = Math.max(maxVal, map.get(key));
        }

        int count = 0;

        for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
            if (pair.getValue() == maxVal) {
                ++count;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int ans = countLargestGroup(13);
        System.out.println(ans);

        ans = countLargestGroup(2);
        System.out.println(ans);

        ans = countLargestGroup(15);
        System.out.println(ans);

        ans = countLargestGroup(24);
        System.out.println(ans);
    }
}
